#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"

using namespace std;
/*HJJ QQ479287006
 6235. 逐层排序二叉树所需的最少操作数目 显示英文描述
通过的用户数1073
尝试过的用户数1558
用户总通过次数1106
用户总提交次数2150
题目难度Medium
给你一个 值互不相同 的二叉树的根节点 root 。

在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。

返回每一层按 严格递增顺序 排序所需的最少操作数目。

节点的 层数 是该节点和根节点之间的路径的边数*
 * */
// C++ program to find
// minimum number of swaps
// required to sort an array
#include<bits/stdc++.h>

using namespace std;

// Function returns the
//寻找数组最少交换次数
// minimum number of swaps
// required to sort the array
int minSwaps(vector<int> arr, int n) {
    // Create an array of
    // pairs where first
    // element is array element
    // and second element
    // is position of first element
    pair<int, int> arrPos[n];
    for (int i = 0; i < n; i++) {
        arrPos[i].first = arr[i];
        arrPos[i].second = i;
    }

    // Sort the array by array
    // element values to
    // get right position of
    // every element as second
    // element of pair.
    sort(arrPos, arrPos + n);

    // To keep track of visited elements.
    // Initialize
    // all elements as not visited or false.
    vector<bool> vis(n, false);

    // Initialize result
    int ans = 0;

    // Traverse array elements
    for (int i = 0; i < n; i++) {
        // already swapped and corrected or
        // already present at correct pos
        if (vis[i] || arrPos[i].second == i)
            continue;
        // find out the number of  node in
        // this cycle and add in ans
        int cycle_size = 0;
        int j = i;
        while (!vis[j]) {
            vis[j] = 1;
            // move to next node
            j = arrPos[j].second;
            cycle_size++;
        }
        // Update answer by adding current cycle.
        if (cycle_size > 0) {
            ans += (cycle_size - 1);
        }
    }

    // Return result
    return ans;
}


int minimumOperations(TreeNode *root) {

    int count = 0;

    if (root == nullptr) {
        return ret;
    }


    queue<TreeNode *> q;

    q.push(root);

    while (!q.empty()) {

        int sizer = q.size();

        vector<int> t;

        for (int i = 0; i < sizer; i++) {
            TreeNode *temp = q.front();
            q.pop();
            if (temp->left) {
                q.push(temp->left);
            }
            if (temp->right) {

                q.push(temp->right);
            }

            t.push_back(temp->val);
        }

        count += minSwaps(t, t.size());

    }


    return count;

}
